package 动态规划;

/**
 * 最长公共子串
 * @author macy
 * @date 2025/7/22 17:13
 */
public class CommonSubString {

    /**
     * 为什么当 str1.charAt(i - 1) != str2.charAt(j - 1) 时，dp[i][j] = 0 而不是 dp[i][j] = dp[i-1][j-1]？
     * 这是因为：
     * 最长公共子串要求连续性：
     * 如果当前字符不相等，说明连续性被打破。
     * 因此，以 str1[i-1] 和 str2[j-1] 结尾的字符无法构成任何公共连续子串的一部分。
     * 所以 dp[i][j] 必须为 0。
     * 不能继承 dp[i-1][j-1] 的值：
     * dp[i-1][j-1] 表示的是以 str1[i-2] 和 str2[j-2] 结尾的最长公共子串长度。
     * 但当前字符不匹配，无法将这个长度延续下来。
     * 如果此时设置 dp[i][j] = dp[i-1][j-1]，则会错误地保留之前的连续长度，导致结果不准确。
     *
     * @param str1
     * @param str2
     * @return
     */
    public static int longestCommonSubstr(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        // 创建一个二维数组 dp，其中 dp[i][j] 表示以 str1[i-1] 和 str2[j-1] 结尾的 最长公共连续子串 的长度
        int[][] dp = new int[m + 1][n + 1];
        int maxLength = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return maxLength;
    }


    public static String longestCommonSubstring(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        // 记录最长子串的长度
        int maxLen = 0;
        // 记录最长子串在 str1 中的结束位置
        int endIdx = 0;

        // 创建一个二维数组 dp，其中 dp[i][j] 表示以 str1[i-1] 和 str2[j-1] 结尾的最长公共子串长度
        int[][] dp = new int[m + 1][n + 1];

        // 填充 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        // 更新最长子串的结束位置
                        endIdx = i;
                    }
                } else {
                    // 不连续时，长度为 0
                    dp[i][j] = 0;
                }
            }
        }

        // 根据 maxLen 和 endIdx 提取最长公共子串
        return str1.substring(endIdx - maxLen, endIdx);
    }

    public static void main(String[] args) {
        String str1 = "abcdef";
        String str2 = "zcdemf";
        System.out.println("最长公共子串长度为: " + longestCommonSubstr(str1, str2));
    }
}
